// class Node {
//   val: number
//   children: Node[]
//   constructor(val?: number) {
//     this.val = (val === undefined ? 0 : val)
//     this.children = []
//   }
// }


// function preorder(root: Node | null): number[] {
//   if (!root) {
//     return [];
//   }
//   const stack = [root];
//   const ret = [];
//   while(stack.length > 0) {
//     let curr = stack.splice(0, 1)[0];
//     ret.push(curr.val);
//     stack=[...curr.children, ...stack];
//   }
//   return ret;
// };

var preorder = function(root) {
  let ret = []
  if(!root) return [];
  const traverse = node => {
      ret.push(node.val);
      if(node.children.length > 0) {
          node.children.forEach(n => traverse(n));
      }
  }
  traverse(root);
  return ret;
};